from typing import List


class Solution:
    def splitArraySameAverage(self, nums: List[int]) -> bool:
        # 如果只有1个数，则一定无法构成
        if len(nums) == 1:
            return False

        # 计算每一个数距离平均值的距离（为避免浮点数影响，全部乘以len(nums)）
        avg = sum(nums)
        nums = [num * len(nums) - avg for num in nums]

        if 0 in nums:
            return True

        # 将数组拆分为两部分
        left_nums = nums[:len(nums) // 2]
        right_nums = nums[len(nums) // 2:]

        # 计算左侧的数组的所有组合
        s1 = len(left_nums)
        left_values = [0 for _ in range(1 << s1)]  # 2**n种可能
        for i in range(s1):
            for j in range(1 << i):
                left_values[(1 << i) + j] = left_nums[i] + left_values[j]

        left_values = set(left_values[1:-1])

        s1 = len(right_nums)
        right_values = [0 for _ in range(1 << s1)]  # 2**n种可能
        for i in range(s1):
            for j in range(1 << i):
                right_values[(1 << i) + j] = right_nums[i] + right_values[j]

        right_values = set(right_values[1:-1])

        # print(left_values, right_values)

        if 0 in left_values:
            return True
        if 0 in right_values:
            return True

        if - sum(left_nums) in right_values:
            return True
        if - sum(right_nums) in left_values:
            return True

        if sum(left_nums) == 0 or sum(right_nums) == 0:
            return True

        for value in left_values:
            if -value in right_values:
                return True

        return False


if __name__ == "__main__":
    print(Solution().splitArraySameAverage([1, 2, 3, 4, 5, 6, 7, 8]))  # True
    print(Solution().splitArraySameAverage([3, 1]))  # False
    print(Solution().splitArraySameAverage([1, 6, 1]))  # False
    print(Solution().splitArraySameAverage([1, 1, 2, 1, 1, 2]))  # True

    # 测试用例58 : True
    print(Solution().splitArraySameAverage([10, 29, 13, 53, 33, 48, 76, 70, 5, 5]))

    # 测试用例59 : False
    print(Solution().splitArraySameAverage(
        [60, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30,
         30, 30]))

    # 测试用例92 : True
    print(Solution().splitArraySameAverage([18, 0, 16, 2]))
